#include<iostream>
#include<string>
using namespace std;
int loopcount = 0;
int* pattern_array = nullptr;
//查找字符串内部匹配表
void StringInerMatchTable(const string& pattern)
{
	const int pattern_length = pattern.size();
	pattern_array = new int[pattern_length];
	//第一个元素，前面没有匹配项
	pattern_array[0] = 0;
	int matchCount = 0;
	int matchIndex = 0;
	for (int i = 1; i < pattern_length; i++)
	{
		loopcount++;
		if (pattern[i] == pattern[matchIndex])
		{
			pattern_array[i] = ++matchCount;
			matchIndex++;
		}
		else
		{
			matchCount = 0;
			matchIndex = 0;
			pattern_array[i] = 0;
		}
		//cout << pattern[i] << ":" << pattern_array[i] << endl;
	}
	
}
int FindMatch(const string& target,const string& pattern)
{
	if (target.size() < pattern.size())
		cout << "error pattern longer than target" << endl;
	int targetLength = target.size();
	int patternIndex = 0;
	int i = 0;
	while (i < targetLength)
	{
		loopcount++;
		if (target[i] != pattern[patternIndex])
		{
			i++;
			continue;
		}
		else
		{
			int localIndex = i+1;
			patternIndex++;
			while (target[localIndex] == pattern[patternIndex])
			{
				loopcount++;
				localIndex++;
				patternIndex++;
			}
			
			if (patternIndex == pattern.size())
				return i;
			else
			{//移动位数 = 已匹配的字符数 - 对应的部分匹配值
				i = patternIndex - pattern_array[patternIndex - 1] + i;
				patternIndex = 0;
				continue;
			}
		}
		i++;
	}
	return -1;
}
int main()
{
	string tartgetstr = "BBC ABCDAB ABCDABCDABDE";
	string pattern = "ABCDABD";
	printf("'%s' size = %d\n", tartgetstr.c_str(), tartgetstr.size());
	printf("'%s' size = %d\n", pattern.c_str(), pattern.size());

	StringInerMatchTable(pattern);
	int matchindex = FindMatch(tartgetstr,pattern);
	cout << "total loopcount = " << loopcount << endl;
	//cout << "match index = " << matchindex << endl;
	for (int i = 0; i < pattern.size(); i++)
		cout << tartgetstr[i + matchindex];
	cout << endl;
	delete[] pattern_array;
	return 0;
}
